DROPS

Document

DOI: 10.4230/LIPIcs.SEA.2018.30

Isomorphism Test for Digraphs with Weighted Edges

Authors: Adolfo Piperno

Published in: LIPIcs, Volume 103, 17th International Symposium on Experimental Algorithms (SEA 2018)

Abstract

Colour refinement is at the heart of all the most efficient graph isomorphism software packages. In this paper we present a method for extending the applicability of refinement algorithms to directed graphs with weighted edges. We use {Traces} as a reference software, but the proposed solution is easily transferrable to any other refinement-based graph isomorphism tool in the literature. We substantiate the claim that the performances of the original algorithm remain substantially unchanged by showing experiments for some classes of benchmark graphs.

Cite as

Adolfo Piperno. Isomorphism Test for Digraphs with Weighted Edges. In 17th International Symposium on Experimental Algorithms (SEA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 103, pp. 30:1-30:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{piperno:LIPIcs.SEA.2018.30,
  author =	{Piperno, Adolfo},
  title =	{{Isomorphism Test for Digraphs with Weighted Edges}},
  booktitle =	{17th International Symposium on Experimental Algorithms (SEA 2018)},
  pages =	{30:1--30:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-070-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{103},
  editor =	{D'Angelo, Gianlorenzo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2018.30},
  URN =		{urn:nbn:de:0030-drops-89659},
  doi =		{10.4230/LIPIcs.SEA.2018.30},
  annote =	{Keywords: Practical Graph Isomorphism, Weighted Directed Graphs, Partition Refinement}
}

Search Results

Documents authored by Piperno, Adolfo

Isomorphism Test for Digraphs with Weighted Edges

Abstract

Cite as

Thanks for your feedback!

Could not send message